package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

import java.util.*;

/**
 * @author tzp
 * @since 2020/9/11
 */
public class LC971 implements TreeProblem {
    public static void main(String[] args) {
        {
            TreeNode node7 = new TreeNode(7);
            TreeNode node15 = new TreeNode(15);
            TreeNode node20 = new TreeNode(20);
            TreeNode node9 = new TreeNode(9);
            TreeNode node3 = new TreeNode(3);
            node3.left = node9;
            node3.right = node20;
            node20.left = node15;
            node20.right = node7;

            int[] ints = {3, 9, 20, 7, 15};
            System.out.println(new LC971().flipMatchVoyage(node3, ints));
        }

        {
            TreeNode node1 = new TreeNode(1);
            TreeNode node2 = new TreeNode(2);
            node1.left = node2;
            int[] ints = {2, 1};
            System.out.println(new LC971().flipMatchVoyage(node1, ints));
        }

    }

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> xx = new ArrayDeque<>();
        xx.add(root);
        int current = 0;
        TreeNode parent = new TreeNode(-1);

        while (xx.size() != 0) {
            TreeNode node = xx.pollFirst();
            if (node == null) {
                return Collections.singletonList(-1);
            }
            if (voyage[current] == node.val) {
                current++;
                if (node.right != null) {
                    xx.addFirst(node.right);
                }
                if (node.left != null) {
                    xx.addFirst(node.left);
                }
                parent = node;
            } else {//发生了flip?
                TreeNode flipPair = xx.pollFirst();
                if (flipPair == null) {
                    return Collections.singletonList(-1);
                }
                if (voyage[current] != flipPair.val) { //关键点
                    return Collections.singletonList(-1);
                }
                result.add(parent.val);
                xx.addFirst(node);//把俩人换位置重新放回去
                xx.addFirst(flipPair);
            }
        }
        return result;
    }
}
